# 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 
# 
#  说明：每次只能向下或者向右移动一步。 
# 
#  
# 
#  示例 1： 
#  
#  
# 输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
# 输出：7
# 解释：因为路径 1→3→1→1→1 的总和最小。
#  
# 
#  示例 2： 
# 
#  
# 输入：grid = [[1,2,3],[4,5,6]]
# 输出：12
#  
# 
#  
# 
#  提示： 
# 
#  
#  m == grid.length 
#  n == grid[i].length 
#  1 <= m, n <= 200 
#  0 <= grid[i][j] <= 200 
#  
# 
#  Related Topics 数组 动态规划 矩阵 👍 1749 👎 0
from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        # m行n列
        m = len(grid)
        n = len(grid[0])
        # dp = [[0]*n for _ in range(m)]
        # dp[0][0] = grid[0][0]
        # for i in range(1,n):
        #     dp[0][i] = dp[0][i-1]+grid[0][i]
        # for j in range(1,m):
        #     dp[j][0] = dp[j-1][0]+grid[j][0]
        # pre = 0
        # for m1 in range(1,m):
        #     for n1 in range(1,n):
        #         dp[m1][n1] = min(dp[m1-1][n1]+grid[m1][n1],dp[m1][n1-1]+grid[m1][n1])
        # return dp[m-1][n-1]
        # "方法2：只用两个元素"

#       从第二行开始遍历
        cur = grid[0]
        for i in range(1,n):
            cur[i]+=cur[i-1]
        # 从第2行开始,精髓：每次只是在一行比较（只要知道元素上方和左方的就行了），所以只用一个一维数组就行了
        for i in range(1,m):
            # 先更新第一列
            cur[0]+=grid[i][0]
            for j in range(1,n):
                cur[j] = min(cur[j],cur[j-1])+grid[i][j]
        return cur[n-1]


# leetcode submit region end(Prohibit modification and deletion)
print(Solution().minPathSum(grid = [[1,3,1],[1,5,1],[4,2,1]]))